# T(n)=O(f(n))
# 1.T(n)表示代码执行时间
# 2.n表示数据规模大小
# 3.f(n)表示每行代码执行的次数总和
# 4.因为这是一个公式,所以用f(n)来表示.公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比
# 5.大O时间复杂度也叫渐进时间复杂度 asymptotic time complexity
# 常见时间复杂度
# 1.O(1)常数阶时间复杂度
# 2.O(n)线性阶时间复杂度
# 3.O(logn)对数阶时间复杂度
# 4.O(nlogn)线性对数阶时间复杂度
# 5.O(n^2)平方阶时间复杂度
# 6.O(n^3)立方阶时间复杂度
# 7.O(2^n)指数阶时间复杂度
# 8.O(n!)阶乘时间复杂度
# 常见时间复杂度效率排序
# O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^2logn)<O(n^3)


# 时间复杂度算法
def fun1(age):
    # 1*unit-time
    if age <= 10:
        print('幼年时间')
    elif age <= 20:
        print('少年时期')
    elif age <= 35:
        print('青年时期')
    elif age <= 60:
        print('中年时期')
    else:
        print('老年时期')


# (1+n+1)*unit-time 时间复杂度O(n) 线性阶
def fun2(n):
    # 执行1次
    sum = 0
    for x in range(n):
        # 执行n次
        sum = sum + x
    # 执行1次
    print(sum)


# 时间复杂度(n^2) 平方阶
def fun3(n):
    for x in range(n):
        # 执行n次
        for y in range(n):
            # 执行n次
            print('***********')


# 最终执行n*20次 时间复杂度O(nlogn)
def fun4(n):
    for x in range(n):
        # 执行n次
        for y in range(20):
            # 执行20次
            print('***********')


# 时间复杂度O(log(n))
def fun5(n):
    # 执行1次
    i = 1
    while i < n:
        # 2^x = n 执行x = log2(n)
        print('***********')
        i = i * 2


# 时间复杂度O(nlog(n))
def fun6(n):
    i = 1
    while i < n:
        for x in range(n):
            print('***********')
        i = i * 2


# 递归调用获取斐波那契第n项值 时间复杂度极高 开销巨大 时间复杂度O(2^n)指数阶
def fun7(n):
    if n <= 1:
        return n
    else:
        return fun7(n - 1) + fun7(n - 2)


# 循环调用获取斐波那契第n项值 时间复杂度O(n)常数阶
def fun8(n):
    list1 = [1, 1]
    if n <= 2:
        return 1
    else:
        for x in range(n - 2):
            list1.append(list1[-1] + list1[-2])
        return list1[-1]


print(fun7(4))
